% PCA - Principal Component Analysis
% Marcelo Barros de Almeida
% 14:31 - 13/Mar/98
\chapter{Principal Component Analysis}
\label{LAB-PCA}
\section{introdu\c{c}\~{a}o}

Apesar de PCA ({\em Principal Component Analysis}) ser um n\~{a}o totalmente 
dentro do contexto de problemas mal colocados, ele se encontra afinado 
com a \'{a}lgebra para sistemas lineares e com os objetivos deste trabalho,
sendo descrito aqui
\footnote{O texto que se segue tem como base principal o livro
de Haykin \cite{HAYKIN9401}.}.

PCA (\textit{Principal Component Analysis}) pode ser considerada uma dos
mais antigos m\'{e}todos de an\'{a}lise multivari\'{a}vel, sendo utilizado pela primeira
vez em 1901, por Pearson, em trabalhos na \'{a}rea biol\'{o}gica \cite{PEARSON0101}.
Trabalhos posteriores na \'{a}rea de probabilidades \cite{KARHUNEN4701,LOEVE6301}
tornaram a t\'{e}cnica ainda mais difundida. Para refer\^{e}ncias mais recentes, ver
o livro de Jolliffe \cite{JOLLIFFE8601}.

PCA pode ser considerado como um
m\'{e}todo para redu\c{c}\~{a}o de dimens\~{a}o sem perdas significativas,
atrav\'{e}s da elimina\c{c}\~{a}o estat\'{\i}stica de componentes redundantes.
Do ponto de vista de classifica\c{c}\~{a}o, PCA pode ser entendido tamb\'{e}m como um
m\'{e}todo estat\'{\i}stico de extra\c{c}\~{a}o de caracter\'{\i}sticas principais.
Aplica\c{c}\~{o}es que exigem grande volume de dados, como processamento de
imagens e sinais, ou que possuam muitas vari\'{a}veis pouco significativas,
s\~{a}o boas candidatas para a utiliza\c{c}\~{a}o desta t\'{e}cnica.

\section{Funcionamento}

O processo b\'{a}sico do PCA consiste em se calcular os autovetores de uma matriz de
correla\c{c}\~{a}o formada atrav\'{e}s do conjunto de dados e utilizar os
autovetores com maiores autovalores associados como base para um novo
sistema de representa\c{c}\~{a}o. Este processo ser\'{a} melhor descrito a seguir.

Inicialmente considere um conjunto de dados no espa\c{c}o $\mathbf{X}$, representados
por $p$ vetores $\mathbf{x}$ de dimens\~{a}o $m$:

\begin{equation}
\mathbf{x_i}=\left[ 
\begin{array}{cccc}
x_1 & x_2 & ... & x_m
\end{array}
\right] ^t
\end{equation}

\'{E} importante que os vetores utilizados em PCA tenham valor esperado zero. 
Caso os dados n\~{a}o estejam desta forma, um tratamento pr\'{e}vio deve ser feito 
neles de forma que isto seja obedecido.

Com estes vetores definidos \'{e} poss\'{\i}vel montar a matriz de correla\c{c}\~{a}o 
$\mathbf{R}$, da seguinte maneira:

\begin{equation}
\mathbf{R}=( \mathbf{x_1}\mathbf{x_1}^t + \mathbf{x_2}\mathbf{x_2}^t + ... + \mathbf{x_p}\mathbf{x_p}^t) / p
\end{equation}

A matriz $\mathbf{R}$ ser\'{a} formada como uma esp\'{e}cie de m\'{e}dia entre as
diversas matrizes provenientes dos produtos $\mathbf{x_i}\mathbf{x_i}^t$. 
Quando os vetores utilizados pertencem todos \`{a} mesma classe, isto 
parece bastante consistente. Mas o que aconteceria
quando os vetores que formam a matriz de correla\c{c}\~{a}o pertencerem a
classes diferentes ? O que fica mais ou menos evidente \'{e} que se deve
 fazer uma agrupamento por classes antes de se partir para a matriz de correla\c{c}\~{a}o. 
Em \cite{TODD9701} \'{e} descrito um m\'{e}todo para isto, 
onde inicialmente s\~{a}o feitas parti\c{c}\~{o}es
para separa\c{c}\~{a}o dos dados em regi\~{o}es disjuntas e depois \'{e}
utilizado PCA em cada regi\~{a}o definida .

Uma vez montada a matriz de correla\c{c}\~{a}o, os seus autovalores e
autovetores s\~{a}o calculados. Os autovetores podem ser considerados como
uma base ortonormal de um novo espa\c{c}o onde os dados ser\~{a}o
representados\cite{HAYKIN9401}. Al\'{e}m disto, tem-se vari\^{a}ncia
m\'{a}xima garantida em cada eixo do novo sistema, sendo que o valor da
vari\^{a}ncia para cada eixo pode ser visto atrav\'{e}s de seu autovalor
associado. Neste novo espa\c{c}o, alguns eixos n\~{a}o possuem valores
consider\'{a}veis para a vari\^{a}ncia e, portanto, podem ser desprezados sem grandes
perdas para a transforma\c{c}\~{a}o inversa.

Seja $\mathbf{W}$ a matriz contendo os $m$ autovetores de $\mathbf{R}$:

\begin{equation}
\mathbf{W}=\left[ 
\begin{array}{cccc}
\mathbf{u_1} & \mathbf{u_2} & ... & \mathbf{u_m}
\end{array}
\right]
\end{equation}

Onde $\mathbf{u_i}=\left[ 
\begin{array}{cccc}
u_{1i} & u_{2i} & ... & u_{mi}
\end{array}
\right] ^t$, tendo ainda autovalor associado $\lambda _i$. Considere
tamb\'{e}m que $\lambda _1\geq \lambda _2\geq ...\geq \lambda _m$.

Desta forma, os dados podem ser representados no novo espa\c{c}o $\mathbf{Y}$ da
seguinte maneira:

\begin{equation}
\mathbf{Y}=\mathbf{W}^t\mathbf{X}
\end{equation}

Um elemento deste espa\c{c}o ter\'{a}, agora, dimens\~{a}o $\left( m\times1\right) $.

A transforma\c{c}\~{a}o inversa pode ser dada por:

\begin{equation}
\mathbf{X}=\mathbf{WY}
\end{equation}

Isto pode ser feito uma vez que $\mathbf{WW}^t=\mathbf{I}$ ($\mathbf{W}$ \'{e} matriz ortonormal).

Considerando-se agora uma matriz $\mathbf{W}_r$ contendo os $n$ maiores autovetores,
($n<m$). Os elementos deste novo espa\c{c}o $\mathbf{Y}_r$ ter\~{a}o sua
dimens\~{a}o reduzida para $\left( n\times 1\right) $. As transforma\c{c}\~{o}es 
diretas e inversas est\~{a}o representadas abaixo: 
\begin{equation}
\mathbf{Y}_r=\mathbf{W}_r^t\mathbf{X}
\end{equation}
\begin{equation}
\mathbf{X}_r=\mathbf{W}_r\mathbf{Y}_r
\end{equation}

\section{Exemplo}

Um exemplo pode ser visto no programa escrito em Matlab, ao final deste
ap\^{e}ndice. Nele, dez padr\~{o}es  $\left( 7\times 5\right) $ do algarismo 0, 
armazenados em vetores de
dimens\~{a}o $\left( 35\times 1\right) $ (Figura \ref{PATTORG}) s\~{a}o
transformados para um novo espa\c{c}o, com vetores agora de dimens\~{a}o 
$\left( 8\times 1\right) $, sem perda na representa\c{c}\~{a}o (Figura \ref
{PATTDIM8}). Como as imagens s\~{a}o bin\'{a}rias, uma fun\c{c}\~{a}o do tipo
degrau \'{e} aplicada no valor obtido pela transforma\c{c}\~{a}o inversa. Valores
menores para a dimens\~{a}o ir\~{a}o produzir padr\~{o}es n\~{a}o exatamente iguais
aos originais (Figura \ref{PATTDIM2}), mas que generalizam o algarismo zero.
Com uma \'{u}nica dimens\~{a}o, tem-se exatamente o algarismo 0 recuperado. \'{E}
evidente que, para este tipo de recupera\c{c}\~{a}o, os dados de entrada devem
estar estatisticamente bem distribu\'{\i}dos.

Um dos poss\'{\i}veis problemas a se enfrentar na utiliza\c{c}\~{a}o PCA est\'{a}
ligado \`{a} dimens\~{a}o das matrizes envolvidas no c\'{a}lculo. 
Para imagens bin\'{a}rias de, por
exemplo, $\left( 640\times 480\right) $, a matriz de correla\c{c}\~{a}o
teria dimens\~{a}o de $\left( 307.200\times 307.200\right) $, aumentando
muito o tempo computacional. Desta forma, outras t\'{e}cnicas para
manipula\c{c}\~{a}o de matrizes e c\'{a}lculo de autovetores se fazem
necess\'{a}rias.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=9cm,height=6cm]{pattorg.ps}
\end{center}
\caption{Padr\~{o}es originais}
\label{PATTORG}
\end{figure}

\begin{figure}[htb]
\begin{center}
\includegraphics[width=9cm,height=6cm]{pattdim8.eps}
\end{center}
\caption{Transforma\c{c}\~{a}o inversa para padr\~{o}es de dimens\~{a}o 8}
\label{PATTDIM8}
\end{figure}

\begin{figure}[tbh]
\begin{center}
\includegraphics[width=9cm,height=6cm]{pattdim2.eps}
\end{center}
\caption{Transforma\c{c}\~{a}o inversa para padr\~{o}es de dimens\~{a}o 2}
\label{PATTDIM2}
\end{figure}

\subsection{Programa}

{\tt

\%\% Exemplo para PCA (Principal Component Analysis)

\%\%

\%\% Marcelo Barros de Almeida

\%\% 11:16 13/Mar/98

clear;

\% Padroes de zero utilizados no treinamento

\%

X1 = [ 0 0 1 1 0 ; 0 1 0 0 1 ; 0 1 0 0 1 ; 0 1 0 0 1 ; 

\qquad\qquad 0 1 0 0 1 ; 0 0 1 0 1 ;0 0 1 0 0 ];

X2 = [ 0 1 1 1 0 ; 0 1 0 1 1 ; 0 1 0 0 1 ; 0 1 0 0 1 ;

\qquad\qquad 1 1 0 0 1 ; 0 1 0 0 1 ;0 0 1 1 0 ];

X3 = [ 0 0 1 1 0 ; 0 1 1 0 1 ; 0 1 0 0 1 ; 0 1 1 0 1 ;

\qquad\qquad  0 1 0 0 0 ; 0 1 0 0 1 ; 0 0 1 1 0 ];

X4 = [ 0 0 0 1 1 ; 0 1 0 0 1 ; 0 1 0 1 1 ; 0 1 0 0 1 ;

\qquad\qquad  0 1 0 0 1 ; 0 1 0 0 1 ; 0 0 1 1 0 ];

X5 = [ 0 0 1 1 0 ; 0 1 0 0 0 ; 0 1 1 0 1 ; 0 1 0 0 1 ; 

\qquad\qquad 0 1 0 0 1 ; 0 1 0 0 1 ; 0 0 1 1 1 ];

X6 = [ 0 0 1 1 0 ; 0 1 0 0 1 ; 0 1 0 0 1 ; 0 1 0 0 1 ; 

\qquad\qquad 0 1 0 0 1 ; 0 0 1 1 1 ; 0 0 1 1 0 ];

X7 = [ 0 0 1 1 0 ; 0 1 0 0 1 ; 0 1 0 0 0 ; 0 1 0 0 1 ; 

\qquad\qquad 0 0 0 0 1 ; 0 1 1 0 1 ; 0 0 1 1 0 ];

X8 = [ 0 0 1 1 0 ; 0 1 1 0 1 ;0 1 1 1 1 ; 0 1 0 0 1 ;

\qquad\qquad 0 1 0 0 1 ; 0 1 0 0 1 ;0 0 1 1 0 ];

X9 = [ 0 0 1 1 0 ; 0 1 0 0 1 ;0 1 0 0 0 ; 0 0 0 0 1 ;

\qquad\qquad 0 1 0 0 1 ; 0 1 0 1 1 ;0 0 1 1 0 ];

X10 =[ 0 0 1 1 1 ; 0 1 1 0 1 ;0 1 0 0 1 ; 0 1 0 0 1 ; 

\qquad\qquad 0 1 0 0 1 ; 0 1 0 0 1 ;0 0 1 1 1 ];


X = [];

\% Plotando os padroes

\%

h1 = figure;

set(h1,'Name','Padroes de zero originais - vetores com 35 elementos');

set(h1,'Position',[10 500 500 300]);

for l=1:2

\qquad    for c=1:5

\qquad\qquad        f = (l-1)*5+c;

\qquad\qquad        eval(sprintf('subplot(2,5,\%1d), image(256*X\%1d)',f,f));

\qquad\qquad        title(sprintf('Padrao \%1d',f));

\qquad\qquad        colormap(gray);

\qquad\qquad        axis image;

\qquad\qquad        axis('off');

\qquad\qquad        \% mudanca de faixa: [0 +1]  ->  [-1 +1]

\qquad\qquad        \% Vetores devem ter media zero

\qquad\qquad        X(:,f) = eval(sprintf('2*X\%1d(:)-1',f));  

\qquad    end

end

\% Gerando matriz de correlacao e calculando autovetores/autovalores

\%

[m,p] = size(X); \% dimensao e numero de padroes

R = zeros(m,m);

for i=1:p;

\qquad    R = R + X(:,i)*(X(:,i))';

end

R = R/p;

[W,D] = eig(R);

\% Ordenando os autovalores e autovetores 

\% correspondentes decrescentemente

\%

av = diag(D);

[j,i] = sort(av);

j = sort((1:m)*(-1))*(-1);

i = i(j);

av = av(i);

W = W(:,i);


\% Numero de dimensoes que serao utilizadas na nova representacao

\%

nd = 8;

\% Nova base

\%

WR = W(:,1:nd);

\% Realizando a transformacao: o novo padrao tem a dimensao (nd x 1)

\%

Y = WR'*X;

\% Realizando a transformacao inversa

\%

Xr = WR*Y;

\% Colocando de volta no padrao [0 1]

\%

Xr = hardlim(Xr); \% neural network toolbox 

\% Plotando os padroes

\%

h2 = figure;

set(h2,'Name',sprintf('Transformacao inversa - vetores com \%2d elementos',nd))

set(h2,'Position',[10 80 500 300])


for l=1:2

\qquad    for c=1:5

\qquad\qquad        f = (l-1)*5+c;

\qquad\qquad        t = reshape(Xr(:,f),7,5);

\qquad\qquad        eval(sprintf('subplot(2,5,\%1d), image(256*t)',f));

\qquad\qquad        title(sprintf('Padrao \%1d',f));

\qquad\qquad        colormap(gray);

\qquad\qquad        axis image;

\qquad\qquad        axis('off');

\qquad    end

end

}  % fim textt



%\subsection{Conclus\~{a}o}

%Utilizar PCA como t\'{e}cnica de redu\c{c}\~{a}o de dimensionalidade se revela
%realmente muito interessante, ainda mais quando o conjunto de dados \'{e}
%complexo. A nova base, por ser ortonormal, simplifica c\'{a}lculos posteriores, 
%al\'{e}m da elimina\c{c}\~{a}o das redund\^{a}ncias do conjunto de dados.
%Dessa forma, o trabalho da rede diminui bastante, gastando-se menos
%empo no treinamento.

